package 二分查找;

public class BinarySearchDemo {
    public static void main(String[] args) {
        /*
        给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target
        写一个函数搜索 nums 中的 target
        如果目标值存在返回下标，否则返回 -1。
         */

        int[] nums = {-1,0,3,5,9,12};

        System.out.println(BinaryMy(nums, 9));


    }

    public static int BinaryMy(int[] nums, int target){
        // 1.令查找区间的开始索引为low，结束索引为high
        // 2.计算区间的中间索引 mid = （low + high）/ 2
        // 3.比较target和nums[mid]的值，如果target更大，那说明需要寻找的数在mid的右边（则更新low的索引为mid+1），反之在左边（则更新high的索引为mid-1）
        // 4.一直重复上面步骤，直至nums[mid]的值和target的值相等
        //  4.1如果一直没有找到nums[mid]的值和target的值相等，当low的值比high的值还要大的时候，说明数组不存在target

        int low = 0;
        int high = nums.length - 1;
        while ( low <= high ){
            int mid = (low + high) / 2;
            if ( nums[mid] < target ){
                low = mid + 1;
            }else if( nums[mid] > target ){
                high = mid - 1;
            }else
                return mid;
        }
        // 数组中没有该数据
        return -1;

    }
}
